#include<iostream>                                     
using namespace std;
typedef char ElementType;
typedef struct BiTNode {
	ElementType data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

BiTree CreatBinTree(char *pre, char *in, int n);                 //先序中序输出后序
void postorder(BiTree T);
                                                                 //1.先序的第一个结点一定是根节点 
int main()                                                       //2.在中序数组中，根节点左边的结点就是跟结点的左孩子，根节点右边的结点就是跟结点的右孩子
{                                                                //3.用递归，把当前结点想象成根节点
	BiTree T;                                                    //4.一直左右分左右分就会找到所有的左孩子和右孩子
	char prelist[100];
	char inlist[100];
	int length;
	cin >> prelist;
	cin >> inlist;
	length = strlen(prelist);
	T = CreatBinTree(prelist, inlist, length);
	postorder(T);
	system("pause");
}

void postorder(BiTree T)                               //后序遍历二叉树
{
	if (T)
	{
		postorder(T->lchild);                         //遍历左孩子
		postorder(T->rchild);                         //遍历右孩子
		cout << T->data;                              //输出当前结点数据
	}
}

BiTree CreatBinTree(char *pre, char *in, int n)
{
	BiTree T;
	int i;
	if (n <= 0) return NULL;
	T = (BiTree)malloc(sizeof(BiTNode));
	T->data = pre[0];
	for (i = 0; in[i] != pre[0]; i++);
	T->lchild = CreatBinTree(pre + 1, in, i);                  //"pre+1"是让先序数组后移一位；中序的直接带入就行;i是中序数组中位于当前结点之前的个数
	T->rchild = CreatBinTree(pre +i+ 1, in + i+1, n - i - 1);  //"pre+i+1"是把先序中当前节点和当前结点的所有左子树结点去掉后所剩的右子树结点;"in+i+1"是中序数组中位于当前结点之后的结点
	return T;                                                  //"n-i-1"是中序数组中位于当前结点后面结点的个数
}